#include <iostream>
using namespace std;

int main(){

}

struct ListNode{
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL){}
};

/**
 * 206  : 递归方式反转链表
 * 时间复杂度 O(n)
   空间复杂度 O(1)
 */
class ReverseLinkedList{
public:
    ListNode* reverseList(ListNode* head) {
		if(head == NULL || head->next == NULL)
			return head;
		ListNode* rhead = reverseList(head->next);

		// head->next此刻指向head后面的链表的尾节点
		// head->next->next = head把head节点放在了尾部
		head->next->next = head;
		head->next = NULL:
		return rhead;
    }
};
